package algorithm;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Random;

/**
 * Created by gmwang on 2018/7/23
 * 常见算法
 * https://blog.csdn.net/a632189007/article/details/78018370
 * https://blog.csdn.net/dxhua1996/article/details/77944214/
 * https://www.cnblogs.com/10158wsj/p/6782124.html?utm_source=tuicool&utm_medium=referral
 */
public class CommonSortAlgorithm {

    /**
     * 冒泡排序
     * bubbleSort
     * 时间复杂度，O的n^2
     * 对于冒泡排序，相信对每个人人都很熟悉，这个是每个学习编程的人都会学习的排序方法
     * 具体的原理就是未排好，自上而下的比较，小的数就往上冒，大的数就往下沉，按理来说冒泡排序总共的次数最多为n(n-1)/2
     */
    public void bubbleSort(int[] array) {
        long nowTime = System.nanoTime();
        int tem = 0;
        //记录最后一次交换的位置
        int lastExchangeIndex = 0;
        //无序数列的边界，每次比较只需要比到这里为止
        int sortBorder= array.length - 1;
            boolean isSorted;
        for (int i = 0; i < array.length - 1; i++) {
            isSorted = true;
            for (int j = 0; j <  sortBorder; j++) {
                if (array[j] > array[j + 1]) {
                    tem = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = tem;
                    isSorted = false;
                    //把无序数列的边界更新为最后一次交换元素的位置
                    lastExchangeIndex = j;
                }
            }
            sortBorder = lastExchangeIndex;
            if(isSorted) break;
        }
        System.out.println("冒泡排序已优化，花费时间(ms):" + (System.nanoTime() - nowTime) / 1000000.0 + "ms");
    }

    public void bubbleSortBase(int[] array) {
        long nowTime = System.currentTimeMillis();
        int tem = 0;
        int sortBorder= array.length - 1;
        for (int i = 0; i < array.length - 1; i++) {
            int jBorder = sortBorder - i;
            for (int j = 0; j <  jBorder; j++) {
                if (array[j] > array[j + 1]) {
                    tem = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = tem;
                }
            }
        }
        System.out.println("冒泡排序未优化，花费时间(s):" + (System.currentTimeMillis() - nowTime) / 1000.0 + "s");
    }

    /**
     * 鸡尾酒排序（冒泡排序升级）
     * @param array
     */
    void cocktailSort(int[] array) {
        long nowTime = System.currentTimeMillis();
        int top = array.length - 1;
        int bottom = 0;
        boolean flag = true;
        int i, j;
        while (flag) {
            flag = false;
            //从小到大，升序
            for (i = bottom; i < top; i++) {
                if (array[i] > array[i + 1]) {
                    CommonSortAlgorithmUtils.swap(array, i, i + 1);
                    flag = true;
                }
            }
            top--;
            //从大到小，降序
            for (j = top; j > bottom; j--) {
                if (array[j] < array[j - 1]) {
                    CommonSortAlgorithmUtils.swap(array, j, j - 1);
                    flag = true;
                }
            }
            bottom++;
        }
        System.out.println("冒泡排序之鸡尾酒排序，花费时间(s):" + (System.currentTimeMillis() - nowTime) / 1000.0 + "s");
    }


    /**
     * 直接插入排序
     * directInsertSort
     *
     * @param array 时间复杂度，O的n^2
     * 直接插入排序就是我们假设前面的数为有序数列，然后有序数列与无序数列的每个数比较，我们可以从右向左比较
     * 当 array[i]<=array[j]=
     */
    public void directInsertSort(int[] array) {
        long nowTime = System.nanoTime();
        int tem = 0;
        for (int i = 1; i < array.length; i++) {
            int j = i - 1;
            tem = array[i];
            for (; j >= 0 && array[j] > tem; j--) {
                array[j + 1] = array[j];//将大于array[i]的数整体后移一单位
            }
            array[j + 1] = tem;
        }
        System.out.println("直接插入排序，花费时间(ms):" + ((System.nanoTime() - nowTime) / 1000000.0) + "ms");
    }

    /**
     * 折半插入排序
     * @param source
     * halfInsertSort
     *
     * @param source 时间复杂度，O的n^2
     * 折半插入排序算法是一种稳定的排序算法，比直接插入算法明显减少了关键字之间比较的次数，
     * 因此速度比直接插入排序算法快，但记录移动的次数没有变，所以折半插入排序算法的时间复杂度仍然为O(n^2)，
     * 与直接插入排序算法相同
     */
    public static void halfInsertSort(int[] source) {
        long nowTime = System.currentTimeMillis();
        int size = source.length;
        for (int i = 1; i < size; i++) {
            // 拿出来
            int temp = source[i];
            int begin = 0; // 标记排好序的数组的头部
            int end = i - 1; // 标记排好序数组的尾部
            // 只要头部一直小于尾部，说明temp还在2个标记范围内
            while (begin <= end) {
                // 取2个标记的中间数据的值
                int mid = (begin + end) / 2;
                // 比较，若比中间值大，则范围缩小一半
                if (temp > source[mid]) {
                    begin = mid + 1;
                    // 否则，范围也是缩小一半
                } else {
                    end = mid - 1;
                }
                // 循环结束时，end<begin,即i应该插入到begin所在的索引
            }
            // 从begin到i，集体后移
            for (int j = i; j > begin; j--) {
                source[j] = source[j - 1];
            }
            // 插入i
            source[begin] = temp;
        }
        System.out.println("折半插入排序，花费时间(s):" + ((System.currentTimeMillis() - nowTime) / 1000.0) + "s");
    }
    /**
     * 希尔排序
     * 针对直接插入排序的下效率问题，有人对次进行了改进与升级，这就是现在的希尔排序。
     * 希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。
     * 首先确定分的组数。
     * 然后对组中元素进行插入排序。
     * 然后将length/2，重复1,2步，直到length=0为止。
     * @param arr
     */
    public void shellSort(int [] arr){
        long nowTime = System.nanoTime();
        int len=arr.length;//单独把数组长度拿出来，提高效率
        while(len!=0){
            len=len/2;
            for(int i=0;i<len;i++){//分组
                for(int j=i+len;j<arr.length;j+=len){//元素从第二个开始
                    int k=j-len;//k为有序序列最后一位的位数
                    int temp=arr[j];//要插入的元素
                    /*for(;k>=0&&temp<arr[k];k-=len){
                        arr[k+len]=arr[k];
                    }*/
                    while(k>=0&&temp<arr[k]){//从后往前遍历
                        arr[k+len]=arr[k];
                        k-=len;//向后移动len位
                    }
                    arr[k+len]=temp;
                }
            }
        }
        System.out.println("希尔排序，花费时间(ms):" + ((System.nanoTime() - nowTime) / 1000000.0) + "ms");
//        System.out.println(Arrays.toString(arr));
    }

    /**
     * 快速排序
     *
     * @param numbers
     * @param start
     * @param end     时间复杂度，O的log2 N
     * 在要排的数（比如数组A）中选择一个中心值key（比如A[0]），通过一趟排序将数组A分成两部分，
     *                其中以key为中心，key右边都比key大，key左边的都key小，然后对这两部分分别重复这个过程，直到整个有序。
     *         整个快排的过程就简化为了一趟排序的过程，然后递归调用就行了。
     * 例如  6 9 8 5 4 7(i=0,j=0)
     * first time: 4 9 8 5 6 7  从左向右，取比6大的（第一个为6），从右向左，取比6小的（第一个为4），交换位置(i=0,j=1)
     * second time: 4 5 8 9 6 7 比6大的第二个元素9，比6小的第二个元素5，交换位置(i=2,j=2)
     * third time: 4 5 8 9 6 7 再继续i > j了,递归原方法，45基准变成4，8967基准变成8(i=2,j=1)
     * forth time: 4 5 7 9 6 8  同上，8和7交换(i=2,j=5)
     * fifth time: 4 5 7 6 9 8  同上，9和6交换(i=3,j=4)
     * 再同上 , 7和6交换。9和8交换。
     */
    public void quickSort(int[] numbers, int start, int end) {
        if (start < end) {
            int base = numbers[start];         // 选定的基准值（第一个数值作为基准值）
            int temp;                          // 记录临时中间值
            int i = start, j = end;
            do {
                while ((numbers[i] < base) && (i < end)) {
                    i++;
                }
                while ((numbers[j] > base) && (j > start)) {
                    j--;
                }
                if (i <= j) {
                    temp = numbers[i];
                    numbers[i] = numbers[j];
                    numbers[j] = temp;
                    i++;
                    j--;
                }
            } while (i <= j);
            if (start < j) {
                quickSort(numbers, start, j);
            }
            if (end > i) {
                quickSort(numbers, i, end);
            }
        }
    }

    /**
     * 基数排序
     * @param d
     * @param array
     *  时间复杂度 O的log2 N
     *  基数排序 运用二维数组来分别比较每一位，个位、十位、百位…
     * 输入10个整数的数组
     */
    private void radixSort(int d,int[] array){
        long nowTime = System.nanoTime();
        int n=1;//代表位数对应的数：1,10,100000...
        int k=0;//保存每一位排序后的结果用于下一位的排序输入
        int[][] bucket=new int[10][array.length];//排序桶用于保存每次排序后的结果，这一位上排序结果相同的数字放在同一个桶里
        int[] num=new int[array.length];//用于保存每个桶里有多少个数字 ,最多为输入数组长度
        while(n<=d)
        {
            for(int e:array) //将数组array里的每个数字放在相应的桶里
            {
                int digit=(e/n)%10;
                bucket[digit][num[digit]]=e;
                num[digit]++;
            }
            for(int i=0;i<array.length;i++)//将前一个循环生成的桶里的数据覆盖到原数组中用于保存这一位的排序结果
            {
                if(num[i]!=0)//这个桶里有数据，从上到下遍历这个桶并将数据保存到原数组中
                {
                    for(int j=0;j<num[i];j++)
                    {
                        array[k]=bucket[i][j];
                        k++;
                    }
                }
                num[i]=0;//将桶里计数器置0，用于下一次位排序
            }
            n*=10;
            k=0;//将k置0，用于下一轮保存位排序结果
        }
        System.out.println("基数排序，花费时间(ms):" + ((System.nanoTime() - nowTime) / 1000000.0) + "ms");
    }

    /**
     * 选择排序
     * @param arr
     * 首先确定循环次数，并且记住当前数字和当前位置。
     * 将当前位置后面所有的数与当前数字进行对比，小数赋值给key，并记住小数的位置。
     * 比对完成后，将最小的值与第一个数的值交换。
     * 重复2、3步。
     * 时间复杂度：
     */
    public void selectSort(int[]arr){
        long nowTime = System.currentTimeMillis();
        int len=arr.length;
        for(int i=0;i<len;i++){//循环次数
            int value=arr[i];
            int position=i;
            for(int j=i+1;j<len;j++){//找到最小的值和位置
                if(arr[j]<value){
                    value=arr[j];
                    position=j;
                }
            }
            arr[position]=arr[i];//进行交换
            arr[i]=value;
        }
        System.out.println("选择排序，花费时间(s):" + ((System.currentTimeMillis() - nowTime) / 1000.0) + "s");
    }
    /**
     * 堆排序
     * 对简单选择排序的优化。
     * 将序列构建成大顶堆。
     * 将根节点与最后一个节点交换，然后断开最后一个节点。
     * 重复第一、二步，直到所有节点断开。
     */

    void heapSort(int[] arr){
        long nowTime = System.currentTimeMillis();
        int lastIndex = arr.length - 1;
        CommonSortAlgorithmUtils.buildMaxHeap(arr, lastIndex );//建立最大堆
        while(lastIndex > 0){
            CommonSortAlgorithmUtils.swap(arr, 0, lastIndex);
            if(--lastIndex == 0)//只剩一个元素，就不用调整堆了，排序结束
                break;
            CommonSortAlgorithmUtils.adjustHeap(arr,0,lastIndex);
        }
        System.out.println("堆排序，花费时间(s):" + ((System.currentTimeMillis() - nowTime) / 1000.0) + "s");
    }
    
    /**
     * 归并排序
     */
    public  void mergeSort(int[] arr, int left, int right) {
        long nowTime = System.currentTimeMillis();
        int t = 1;// 每组元素个数
        int size = right - left + 1;
        while (t < size) {
            int s = t;// 本次循环每组元素个数
            t = 2 * s;
            int i = left;
            while (i + (t - 1) < size) {
                CommonSortAlgorithmUtils.merge(arr, i, i + (s - 1), i + (t - 1));
                i += t;
            }
            if (i + (s - 1) < right)
                CommonSortAlgorithmUtils.merge(arr, i, i + (s - 1), right);
        }
        System.out.println("归并排序，花费时间(s):" + ((System.currentTimeMillis() - nowTime) / 1000.0) + "s");
    }

    /**
     * 获取基数排序中的基数
     * @param array
     * @return
     */
    public int getRadixBasicNumber(int[] array){
        if(array == null && array.length ==0) {
            return 0;
        }
        int max =0;
        //1获取最大的绝对值的数
        for(int i =0;i<array.length;i++) {
            if(Math.abs(max)<Math.abs(array[i])) {
                max = array[i];
            }
        }
        int times = 0;
        if(max<0) max = -max;
        //2求出最大的绝对值的数，是10的times次幂。
        while(max >0) {
            max = max/10;
            times ++;
        }
        return times;
    }
    @Test
    public void test() {
        //随机10w 数据
        int[] arrayBubble = new int[1000000];
        int[] arrayBubbleBase = new int[1000000];
        int[] arrayCocktail = new int[1000000];
        int[] arrayInsert = new int[1000000];
        int[] arrayHalfInsertSort = new int[100000];
        int[] arrayShell = new int[1000000];
//        int[] arrayQuick = new int[1000000];
        int[] arrayRadix = new int[1000000];
        int[] arraySelect = new int[100000];
        int[] arrayHeap = new int[100000];
        int[] arrayMerge = new int[100000];
        for (int i = 0; i < 1000000; i++) {
            int ii = new Random().nextInt(10000);
//            arrayBubble[i] = ii;
//            arrayBubbleBase[i] = ii;
//            arrayCocktail[i] = ii;
//            arrayInsert[i] = ii;
//            arrayHalfInsertSort[i] = ii;
//            arrayShell[i] = ii;
//            arrayQuick[i] = ii;
//            arrayRadix[i] = ii;
//            arraySelect[i] = ii;
//            arrayHeap[i] = ii;
//            arrayMerge[i] = ii;
        }
//        bubbleSortBase(arrayBubbleBase);
        //冒泡排序
//        bubbleSort(arrayBubble);
        //鸡尾酒排序
//        cocktailSort(arrayCocktail);
        //直接插入排序
//        directInsertSort(arrayInsert);
        //折半插入排序
//        halfInsertSort(arrayHalfInsertSort);
        //希尔排序
        shellSort(arrayShell);
//        System.out.println(Arrays.toString(arrayInsert));
//        //快速排序
        long nowTime = System.nanoTime();
        int[] arrayQuick =  {6,9,8,5,4,7};
        quickSort(arrayQuick, 0, arrayQuick.length - 1);
        System.out.println("快速排序，花费时间(ms):" + (System.nanoTime() - nowTime)/1000000 + "ms");
//        int [] x = {25 ,11 ,22 ,34 ,15 ,44 ,76, 66, 100, 8 ,14, 20 ,2, 5 ,1 };
//        System.out.println(getRadixBasicNumber(x));
        //基数排序
        radixSort(getRadixBasicNumber(arrayRadix),arrayRadix);
//        System.out.println(Arrays.toString(arrayRadix));
//        //选择排序
//        selectSort(arraySelect);
////        int[] arrayHeap2 = {1, 3, 2, 5, 7, 6, 9, 4, 10};
//        //堆排序
//        heapSort(arrayHeap);
//        //归并排序
//        mergeSort(arrayMerge,0,arrayMerge.length/10);
    }
}
